// 输入：head = [4,2,1,3]
// 输出：[1,2,3,4]

// 合并链表 以及快排
var sortList = function(head) {
    // 合并链表
    let mergeList = (left,right) => {
        // console.log(left)
        // console.log(right)
        // 从最小的块开始合并
        let res = new ListNode(0);
        let pre = res;
        // 排序
        while(left && right){
            if(left.val <= right.val){
                pre.next = left;
                left = left.next;
            }else{
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        // 最大值
        pre.next = left || right;
        // 返回最后的结果
        return res.next;
    }
    // 切分列表
    let mergeSort = (node) => {
        // 若无链表 -> 直接返回
        if(!node || !node.next) return node;

        // 慢指针
        let mid = node;
        // 快指针
        let fast = node.next;

        // 利用fast和fast.next
        // 如果链表长度为奇数，则返回中间节点
        // 如果链表长度为偶数，则有两个中间节点，这里返回第一个
        while(fast && fast.next){
            mid = mid.next;
            fast = fast.next.next;
        }

        // 分割左右链表
        let rightList = mid.next;
        // 从中间切断
        mid.next = null;
        let left = node;
        let right = rightList;
        // 继续分割到只有一个时 -> 传入mergeList合并方法
        return mergeList(mergeSort(left),mergeSort(right));
    }
    // 调用方法
    return mergeSort(head);
};